package alogrithm.solution;

import java.util.ArrayList;

/*
 * 27.跳台阶问题
题目：一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。
求总共有多少总跳法，并分析算法的时间复杂度。

这道题最近经常出现，包括MicroStrategy等比较重视算法的公司都
曾先后选用过个这道题作为面试题或者笔试题。
 */
public class P27 {
	public static ArrayList<ArrayList<Integer>> getAllStepsSolution(int n)
	{
		if(n==0)
		{
			ArrayList<ArrayList<Integer>> result=new ArrayList<>();
			result.add(new ArrayList<Integer>());
			return result;
		}
		else if(n>0)
		{
			ArrayList<ArrayList<Integer>> result=new ArrayList<>();
			ArrayList<ArrayList<Integer>> tmp1=getAllStepsSolution(n-2);
			if(tmp1!=null)
			{
				for(ArrayList<Integer> list:tmp1)list.add(2);
				result.addAll(tmp1);
			}
			tmp1=getAllStepsSolution(n-1);
			if(tmp1!=null)
			{
				for(ArrayList<Integer> list:tmp1)list.add(1);
				result.addAll(tmp1);
			}
			return result;
		}
		return null;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		for(ArrayList<Integer> i:getAllStepsSolution(4))
			System.out.println(i);

	}

}
